package leetcode;

/**
 * @Project : AlgorithmLearning
 * @Package : Leetcode
 * @File : Q1049.java
 * @Author : WangRuoyu
 * @Date 2023/11/5 22:42
 */


public class Q1049 {
    public int lastStoneWeightII(int[] stones) {
        int sum = 0;
        for (int stone : stones) {
            sum += stone;
        }
        boolean[] f = new boolean[sum + 1];
        f[0] = true;
        for (int i = 0; i < stones.length; i++) {
            for (int j = sum; j >= 0; j--) {
                if (j >= stones[i]) f[j] |= f[j - stones[i]];
            }
        }
        for (int l = sum / 2, r = (sum + 1) / 2; l >= 0 && r <= sum; l--, r++) {
            if (f[l]) return sum - 2 * l;
            if (f[r]) return 2 * r - sum;
        }
        return sum;
    }

    public static void main(String[] args) {
        Q1049 sl = new Q1049();
        int[] stones = {31, 26, 33, 21, 40};
        System.out.println(sl.lastStoneWeightII(stones));
    }
}